/**
 * 
 */
package implementations;

import interfaces.Edge;
import interfaces.Vertex;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * @author Kai Bielenberg (kai.bielenberg@haw-hamburg.de)
 * 
 */
public abstract class AbstractUndirectedGraph<E, V> extends AbstractGraph<E, V> {

	@Override
	public String traverse() { // Ausgabe Graph
		Vertex<V> v = edges().iterator().next().start();
		return traverse_(v, new HashSet<Edge<E, V>>(this.edges()),
				calcIncidenceList(), 0);
	}

	public boolean isDirected() {

		return false;
	}

	protected String traverse_(Vertex<V> v, Set<Edge<E, V>> s,
			Map<Vertex<V>, Set<Edge<E, V>>> i, int indent) {
		String result = "";
		String space = "";
		// Leerzeichen zum Einruecken wenn neuer Weg gegangen wird. Je nach
		// Verschachtelungstiefe wird dann weiter eingerueckt.
		for (int n = 0; n < indent; n++) {
			space += "      ";
		}
		result += v + "\n";
		for (Edge<E, V> e : i.get(v)) {
			if (s.remove(e)) {
				result += (" " + space + "-" + e + "-");
				// Sonderfall Schleife: Hier muss die Verschachtelungstiefe um
				// einen zur�ckgesetzt werden, daher indent -=1;
				if (v.equals(e.otherVertex(v))) {
					indent -= 1;
				}
				result += traverse_(e.otherVertex(v), s, i, indent + 1);
			}
		}
		return result;
	}
	
	@Override
	public boolean hasEulerTour(){
		boolean result=true;
		Map<Vertex<V>, Set<Edge<E, V>>> incidenceList = calcIncidenceList();
		Iterator<Map.Entry<Vertex<V>, Set<Edge<E,V>>>> iterator = incidenceList.entrySet().iterator();
		int counter = 0;
		int vertexDegree = 0;
		while(iterator.hasNext()){
		    vertexDegree = iterator.next().getValue().size();
		    if (vertexDegree % 2 != 0) {  
		        counter++;
		        result = false;
		    }
		    
			
		}
		if (counter==2) result=true;
		return result;
	}
	

}
